package org.sudoku.solver;

import java.util.ArrayList;
import java.util.Arrays;

import static org.sudoku.solver.Sudoku.*;

;

/**
 * A simple sudoku solver program. It does not guarantee anything if the input
 * problem is bad. It may halt if there is no progress by inference.
 * 
 * @author shivkumar cm
 */
public class SimpleSolver extends BaseSolver implements I9X9Solver {

	/**
	 * Grid of digits. Only indexes from 1 to 9 are used.
	 */
	protected int m_grid[][] = new int[GRID_SIZE][GRID_SIZE];

	/**
	 * Count of known cells.
	 */
	protected int m_knownCells = 0;

	/**
	 * Intermediate list of inferred cells in one run - int triples of [row,
	 * col, inferred_value]
	 */
	protected ArrayList<int[]> m_inferred = new ArrayList<int[]>();

	/**
	 * Cell processor.
	 */
	protected interface ForeachCell {
		void process(int row, int col);
	}

	/**
	 * Invokes the cell processor for each cell in the grid.
	 */
	protected void foreachCell(ForeachCell processor) {
		for (int i = SUDOKU_BASE; i <= SUDOKU_MAX; ++i) {
			for (int j = SUDOKU_BASE; j <= SUDOKU_MAX; ++j) {
				processor.process(i, j);
			}
		}
	}

	/**
	 * Initialize each cell to BLANK value.
	 */
	private void init() {
		foreachCell(new ForeachCell() {
			public void process(int row, int col) {
				m_grid[row][col] = BLANK;
			};
		});
	}

	public SimpleSolver() {
		init();
	}

	public int get(int row, int col) {
		if (isKnown(row, col)) {
			return -m_grid[row][col];
		} else {
			return UNKNOWN;
		}
	}

	/**
	 * A known cell value is stored in the cell as a negated value. This method
	 * sets the digit to the given [row, col] position. It also notes down the
	 * implications of setting the given cell to this digit- i.e. no other cell
	 * in the same row, col or cube can have the same digit.
	 * 
	 * 
	 * IMPORTANT NOTE: No change if cell value is already known.
	 */
	public void set(int row, int col, int digit) {
		if (isKnown(row, col)) {
			return;
		}
		m_grid[row][col] = -digit;
		setNot4Col(col, digit);
		setNot4Row(row, digit);
		setNot4Cube(row, col, digit);
		++m_knownCells;
	}

	/**
	 * Notes the implied fact that no cell in this column can have this digit as
	 * its value.
	 */
	private void setNot4Col(int col, int digit) {
		for (int i = SUDOKU_BASE; i <= SUDOKU_MAX; ++i) {
			setNot(i, col, digit);
		}
	}

	/**
	 * Notes the implied fact that no cell in this row can have this digit as
	 * its value.
	 */
	private void setNot4Row(int row, int digit) {
		for (int i = SUDOKU_BASE; i <= SUDOKU_MAX; ++i) {
			setNot(row, i, digit);
		}
	}

	/**
	 * Notes the implied fact that no cell in this cube can have this digit as
	 * its value.
	 */
	private void setNot4Cube(int row, int col, int digit) {
		int rowBase = cubeBase(row), colBase = cubeBase(col);
		for (int i = rowBase; i < rowBase + CUBE_SIZE; ++i) {
			for (int j = colBase; j < colBase + CUBE_SIZE; ++j) {
				setNot(i, j, digit);
			}
		}
	}

	/**
	 * Turns off the respective bit in the bit string, i.e., when the cell value
	 * is unknown.
	 */
	void setNot(int row, int col, int digit) {
		if (!isKnown(row, col)) {
			m_grid[row][col] &= ~(1 << digit);
		}
	}

	public boolean isKnown(int row, int col) {
		return m_grid[row][col] < 0;
	}

	/**
	 * Pretty prints the grid showing only the known cells.
	 */
	public void prettyPrint() {
		System.out.println(this.toString());
	}

	public String toString() {

		class CellPrinter implements ForeachCell {
			StringBuffer buffer = new StringBuffer();

			public void process(int row, int col) {
				if (isKnown(row, col)) {
					buffer.append(" " + -m_grid[row][col]);
				} else {
					buffer.append(" _");
				}
				if (col % CUBE_SIZE == 0) {
					buffer.append(" |");
				}
				if (col % SUDOKU_SIDE == 0) {
					buffer.append("\n");
				}
			};
		}
		CellPrinter cellPrinter = new CellPrinter();

		foreachCell(cellPrinter);
		return cellPrinter.buffer.toString();
	}

	/**
	 * Validates and reads the input problem.
	 */
	public void readProblem(final String[] problem) {
		if (problem == null || problem.length != SUDOKU_MAX) {
			throw new IllegalArgumentException(MSG_WRONG_NUM_STRINGS);
		}

		for (String row : problem) {
			if (row.length() != SUDOKU_MAX) {
				throw new IllegalArgumentException(MSG_WRONG_STRING_LENGTH);
			}
		}
		foreachCell(new ForeachCell() {
			public void process(int row, int col) {
				char character = problem[row - 1].charAt(col - 1);
				int digit = character - CHAR_BASE + 1;
				if (character != CHAR_BLANK
						&& !(character >= CHAR_BASE && digit <= CHAR_MAX)) {
					throw new IllegalArgumentException(MSG_ILLEGAL_CHARACTER);
				}
				if (character != CHAR_BLANK) {
					set(row, col, digit);
				}
			}
		});
	}

	/**
	 * @see ISolver#infer()
	 */
	public boolean infer() {
		m_inferred.clear();
		foreachCell(new ForeachCell() {
			public void process(int row, int col) {
				int index = Arrays.binarySearch(INFERRED, m_grid[row][col]);
				if (index >= 0) {
					m_inferred.add(new int[] { row, col, index });
					System.out.println("Inferred " + index + " at [" + row
							+ "][" + col + "]");
				}
			}
		});
		return m_inferred.size() > 0;
	}

	/**
	 * @see ISolver#getInferences()
	 */
	public int[][] getInferences() {
		int inferences[][] = new int[m_inferred.size()][], i = 0;
		for (int[] triplet : m_inferred) {
			inferences[i++] = triplet;
		}
		return inferences;
	}

	/**
	 * @see ISolver#applyInferences()
	 */
	public void applyInferences() {
		System.out.println("Applying inferences...");
		for (int[] triplet : m_inferred) {
			set(triplet[ROW], triplet[COL], triplet[DIGIT]);
		}
	}

	public boolean solved() {
		return m_knownCells == CELL_COUNT;
	}

	/**
	 * Reads the problem on the command-line as an array of strings and solves
	 * it in steps.
	 * 
	 * @param args
	 *            Input the problem as a list of 9 strings. Each string should
	 *            be of length 9 characters. Use characters '1' through '9'. Use
	 *            '0' for theunknowns or blanks.
	 */
	public static void main(String args[]) {
		SimpleSolver solver = new SimpleSolver();
		try {
			solver.readProblem(args);
			System.out.println("\nInitial problem: ");
			solver.prettyPrint();
			solver.solve();
		} catch (IllegalArgumentException ex) {
			System.out
					.println("Usage: Input the problem as a list of 9 strings. "
							+ "Each string should be of length 9 characters. "
							+ "Use characters '1' through '9'. Use '0' for the "
							+ "unknowns or blanks.");
		} catch (Throwable e) {
			System.out
					.println("An unexpected exception has ocurred...Aborting");
			System.out.println(e.getMessage());
			e.printStackTrace();
		}
	}
}
